"""
  10阶楼梯，每次上1个台阶或者2个台阶，问一共有多少种走法

  假设是3阶：
     1 1 1
     1 2
     2 1
   4
     1 1 1 1
     1 2 1
     2 1 1
     2 2

   2
     1 1
     2

  f(n) = f(n - 1) + f(n - 2)

  n = 0  f(n) = 1
  n = 1  f(n) = 1
  n = 2  f(n) = 2


"""

def climb_stairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climb_stairs(n - 1) + climb_stairs(n - 2)

# 测试
n = 10
print(f"{n} 阶楼梯的走法共有 {climb_stairs(n)} 种")  # 输出 89

